/*
 * @lc app=leetcode.cn id=42 lang=cpp
 *
 * [42] 接雨水
 *
 * 方法1：双指针前后夹击 -> 处理中间为最高峰的情况
 *
 * 方法2：单调栈 -> 保证栈内元素单调递减
 */

#include <vector>
#include <stack>
#include <iostream>

// @lc code=start
class Solution
{
public:
    // int trap_01(std::vector<int> &height)
    // {
    //     int volume = 0;

    //     auto i = height.begin();
    //     auto j = height.end() - 1;
    //     int h0 = 0;
    //     while (i != j)
    //     {
    //         if (*i < *j)
    //         {
    //             h0 = *i;
    //             auto k = i + 1;
    //             /* 寻找水坑 */
    //             while (*k < h0 && k != j)
    //                 k++;
    //             /* 计算水坑容积 */
    //             while (i != k)
    //             {
    //                 volume += (h0 - *i);
    //                 i++;
    //             }
    //         }
    //         else
    //         {
    //             h0 = *j;
    //             auto k = j - 1;
    //             /* 寻找水坑 */
    //             while (*k < h0 && k != i)
    //                 k--;
    //             /* 计算水坑容积 */
    //             while (j != k)
    //             {
    //                 volume += (h0 - *j);
    //                 j--;
    //             }
    //         }
    //     }

    //     return volume;
    // }

    int trap(std::vector<int> &height)
    {
        int volume = 0;
        std::stack<int> decrease_stack;

        int top = 0, len = height.size();
        for (int i = 0; i < len; i++)
        {
            /* 保证栈单调 */
            while (!decrease_stack.empty() &&
                   height[i] > height[decrease_stack.top()])
            {
                top = decrease_stack.top();
                decrease_stack.pop();
                if (decrease_stack.empty()) break;

                /* 水量计算 */
            }
            decrease_stack.push(i);
        }

        return volume;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<int> height = {1};

    std::cout << solution.trap(height) << std::endl;

    return 0;
}